Here's the code that Sir gave:
In [7]:
#-----------Node Definitation-------------
class Node():
def __init__(self,value):
self.val=value
self.next=None
#-----------Linked List Definition--------
class LinkedList():
def __init__(svayam):
svayam.head=None
def insert(self,val):
temp=Node(val)
temp.next=self.head
self.head=temp
def printL(self):
temp=self.head
print "Head <--",
while temp!=None:
print temp.val, "<--",
temp=temp.next
print "Tail\n"
def delete(self,v):
if self.head == None:
print "Empty List"
return
if self.head.val==v:
self.head=self.head.next
return
prev=self.head
cur=self.head.next
while cur!=None and cur.val!=v:
cur=cur.next
prev=prev.next
if cur==None:
print "Not found"
else:
prev.next=cur.next
def print_tree(root):
'''Print the tree rooted at root.'''
print_helper(root, "")
def print_helper(root, indent):
'''Print the tree rooted at BTNode root. Print str indent (which
consists only of whitespace) before the root value; indent more for the
subtrees so that it looks nice.'''
if root is not None:
print_helper(root.right, indent + " ")
print " " +indent + "/"
print indent + str(root.val)
print " " +indent + "\\"
print_helper(root.left, indent + " ")
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
#--------- Menu --------------------
ll=LinkedList()
option = 0
while option != 4:
print "1. Add 2. Delete 3. Print 4. Exit"
option=input("Option :")
if option==1:
value=input("What Value to add: ")
ll.insert(value)
elif option==2:
value=input("What Value to delete: ")
ll.delete(value)
elif option==3:
ll.printL()
elif option==4:
break
else:
print "Wrong Option"
Q1. Linked List in Sorted order In a ordinary linked list the elements does not have any order. Thus if we want to sort the elements in a linked list it might take O(n log n) time. But if the elements are stored in sorted order the runtime can be reduced. Write a program to store elements in sorted order. Your program must support the following functions a) Insertion (this is the place where you need to store the incoming element in its correct place) b) Search if an element is present in the list c) Deletion (only one occurrence is deleted) e) Print (prints the list in sorted order). The program should show a menu to the user
If the user picks 1, your program should then ask Value of the new element ?: , etc. Once an operation is finished it must go back to the menu. Example of a menu based program is given below. (filename: LinkedList)
In [4]:
from random import randint
class SortedLinkedList(LinkedList):
def __init__(svayam):
svayam.head=None
svayam.first_node = None
def insert(self,val):
temp=Node(val)
temp_head = self.head
if self.head == None:
self.first_node = temp
self.head = temp
return None
temp_head_prev = None
while temp_head!=None and temp_head.val < val:
temp_head_prev = temp_head
temp_head = temp_head.next
temp.next = temp_head
if temp_head_prev != None:
temp_head_prev.next = temp
else: self.first_node =temp
self.head=self.first_node
#--------- Menu --------------------
ll=SortedLinkedList()
option = 0
while option != 5:
print "1. Add 2. Delete 3. Print 4. Random Testing 5. Exit"
option=input("Option :")
if option==1:
value=input("What Value to add: ")
ll.insert(value)
elif option==2:
value=input("What Value to delete: ")
ll.delete(value)
elif option==3:
ll.printL()
elif option == 4:
print "Random Sequence: ",
for i in range(15):
num = randint(0,9)
print num," ,",
ll.insert(num)
print "\n"
ll.printL()
elif option==5:
break
else:
print "Wrong Option"
The array implementation of stack cannot handle more elements than the size of the array. This can be avoided if the stack is implemented using a linked list. Support Push, Pop and IsEmpty operations. Write a menu based program. (filename:StackUsingLinkedList)
In [5]:
from random import randint
class StackUsingLinkedList(LinkedList):
def __init__(svayam):
svayam.head=None
def isEmpty(self):
if self.head == None:
return True
return False
def Push(self, val):
self.insert(val)
def Pop(self):
if(self.isEmpty()):
return "Underflow Error"
else:
val = self.head.val
self.head = self.head.next
return val
stack=StackUsingLinkedList()
option = 0
while option != 5:
print "\n1. Push 2. Pop 3. Print 4. Random Testing 5. Exit"
option=input("Option :")
if option==1:
value=input("What Value to Push: ")
stack.Push(value)
elif option==2:
print "Popped: ", stack.Pop()
elif option==3:
stack.printL()
elif option == 4:
print "Operation Sequence | Result ",
for i in range(15):
num = randint(0,9)
operation = randint(1,2)
if operation == 1:
print "Push: ", num
stack.Push(num)
elif operation ==2:
print "Pop: ", stack.Pop()
print "\n"
stack.printL()
elif option==5:
break
else:
print "Wrong Option"
Write a program to implement binary search tree. Support:
Again write a menu base program. (filename: BST)
Answer: From Thomas Coreman, we have following pseduo code:
In [ ]:
class BinarySearchTree:
def __init__(self):
""" create an empty binary search tree """
self.root = None
def search(self ,val):
return self.recurive_search(self.root, val)
def recurive_search(self, node, val):
if node == None or val == node.val : return node
if val < node.val:
return self.recurive_search(node.left , val)
else: return self.recurive_search(node.right , val)
def tree_minimum(self, node):
while node.left != None:
node = node.left
return node
def addition(self ,val):
new_node = TreeNode(val)
y = None
x = self.root
while x != None:
y=x
if new_node.val < x.val: x = x.left
else: x = x.right
new_node.parent = y
if y == None: self.root = new_node
else:
if new_node.val < y.val: y.left = new_node
else: y.right = new_node
def deletion(self ,node):
if node.left == None or node.right == None: y = node
else : y = self.successor(node)
if y.left == None: x = y.left
else: x = y.right
if x == None: x.parent = y.parent
if y.parent == None: self.root = x
elif y == y.parent.left: y.parent.left = x
else: y.parent.right = x
if y!= node: node.val = y.val
return y
def successor(self ,node):
if node.right != None: return self.tree_minimum(node)
y = node.parent
while y != None and node == y.right:
node = y
y = y.parent
return y
bst=BinarySearchTree()
option = 0
while option != 6:
print "\n1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit"
option=input("Enter Option :")
if option==1:
value=input("What Value to add: ")
bst.addition(value)
elif option==2:
value=input("What Value to delete: ")
bst.deletion(TreeNode(value))
elif option==3:
value=input("What Value to search: ")
temp = bst.search(value)
if temp == None: print "Not Found"
else: print "Found"
elif option==4:
print "Printing tree in left to right fashion"
print_tree(bst.root)
elif option==5:
value=input("Whos Successor: ")
node = bst.successor(bst.search(value))
if node == None :print "No successor"
else: print "Successor is: ", node.val
elif option==6:
break
else:
print "Wrong Option"
In this program the computer takes input from the user before performing any operation. The operations that need to be supported are 1. Move 2. Add 3. Print. The program shows a menu:
If the user picks 1, then the program asks for a movement pattern. For example if the user gives “LLRRL” the program starts from the current node and moves left, again to the left followed by two right movements and finally a left movement. If the movement is not possible then it reports that and stays in the current node otherwise the current node is updated. Further movement starts from the new node. A movement pattern is a string with letters L, R, P, r where L=left, R=Right, P=Parent, r=root. In operation 2 the program tries to add a new node to the left or right of the current node. If the user picks 2, the program asks “Left or Right?”. Suppose the user picks “L” then if the left child of the current node is “Nil” it asks for a value and adds a node with the value as the left child of the current node. If the left child is not nil, it says “Cannot Add, Place not empty”. The print operation prints the binary tree. The output should match the picture of the tree. For example the text based console output may look like
10
/\
/ \
20 11
/ \
/ \
2 8
2
In [8]:
class SearchTreeCrawler():
def __init__(self):
""" create an empty binary search tree """
self.root = None
self.current = None
def move(self, code):
if self.current == None or self.root == None: print "\n No node exists."
elif code == 'L':
if self.current.left == None: print "\n Cannot Move to: ",code,". Node doesn't exists. Executing Next command.."
else:
self.current = self.current.left
elif code == 'R':
if self.current.right == None: print "\n Cannot Move to: ",code,". Node doesn't exists. Executing Next command .."
else: self.current = self.current.right
elif code == 'P':
self.current = self.current.parent
elif code == 'r':
self.current = self.root
def add(self, val):
temp = TreeNode(val)
if self.root == None:
self.root = temp
self.current = self.root
else:
option = raw_input("L for Left, R for Right: ")
if option == "L":
if self.current.left !=None:
print "\n Cannot Add, Place not empty"
return None
self.current.left = temp
temp.parent = self.current
elif option == "R":
if self.current.right !=None:
print "\n Cannot Add, Place not empty"
return None
self.current.right = temp
temp.parent = self.current
else: print "\n Invalid Selection"
def add_test(self, val, option):
temp = TreeNode(val)
if self.root == None:
self.root = temp
self.current = self.root
else:
if option == "L":
if self.current.left !=None:
print "\n Cannot Add, Place not empty"
return None
self.current.left = temp
temp.parent = self.current
elif option == "R":
if self.current.right !=None:
print "\n Cannot Add, Place not empty"
return None
self.current.right = temp
temp.parent = self.current
else: print "\n Invalid Selection"
bt = SearchTreeCrawler()
option = 0
while option != 5:
print "\n1. Move, 2. Add, 3. Print , 4. Random Testing, 5. Exit "
if bt.current != None: print "Current Node is: ", bt.current.val
option=input("Enter Option :")
if option==1:
value=raw_input("Give movement Pattern: ")
commands = list(value)
for code in commands:
bt.move(code)
elif option==2:
value=input("What Value to add: ")
bt.add(value)
elif option==3:
print "\nPrinting tree in left to right fashion:\n"
print_tree(bt.root)
elif option == 4:
from random import randint
for i in range(4):
num = randint(0,99)
opt = i % 2
if opt == 0: bt.add_test(num, 'L')
else: bt.add_test(num, 'R')
print_tree(bt.root)
elif option==5:
break
else:
print "Wrong Option"